package com.leetcode.partition1;

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @author `RKC`
 * @date 2022/3/18 9:48
 */
public class LCP13寻宝_bfs {

    private static final int N = 10, M = 16;
    private static final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private static char[][] g = new char[N][N];
    //gp[i][j]只记录对应的机关的编号，编号从1开始
    private static int[][] gp = new int[N][N];
    private static Queue<Node> q = new ArrayDeque<>(N);
    private static boolean[][][][] st = new boolean[N][N][1 << M][M];

    private static int n, m, cnt = 1, sx, sy, ex, ey;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine());
        String[] maze = new String[n];
        for (int i = 0; i < n; i++) maze[i] = reader.readLine();
        writer.write(minimalSteps(maze) + "\n");
        writer.flush();
    }

    public static int minimalSteps(String[] maze) {
        n = maze.length;
        m = maze[0].length();
        int sst = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = maze[i].charAt(j);
                if (g[i][j] == 'M') {
                    sst |= 1 << (cnt - 1);
                    gp[i][j] = cnt++;
                } else if (g[i][j] == 'S') {
                    sx = i;
                    sy = j;
                } else if (g[i][j] == 'T') {
                    ex = i;
                    ey = j;
                }
            }
        }
        q.add(new Node(sx, sy, 0, sst, 0));
        while (!q.isEmpty()) {
            Node cur = q.poll();
            int x = cur.x, y = cur.y, d = cur.w, cst = cur.st;
            if (st[x][y][cst][cur.stone]) continue;
            st[x][y][cst][cur.stone] = true;
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m || g[nx][ny] == '#') continue;
                if (nx == ex && ny == ey && cst == 0) return d + 1;
                if (g[nx][ny] == 'M') {
                    int id = gp[nx][ny];
                    //检查手上是否还有石头，如果有石头就放在这，继续走
                    Node next = null;
                    if (cur.stone > 0) {
                        next = new Node(nx, ny, d + 1, cst ^ 1 << (id - 1), cur.stone - 1);
                    } else {
                        //手上没有石头则不能启动机关
                        next = new Node(nx, ny, d + 1, cst, cur.stone);
                    }
                    q.add(next);
                } else if (g[nx][ny] == 'O' && cur.stone == 0) {
                    q.add(new Node(nx, ny, d + 1, cst, cur.stone + 1));
                } else {
                    q.add(new Node(nx, ny, d + 1, cst, cur.stone));
                }
            }
        }
        return -1;
    }

    private static class Node {
        private int x, y, w, st, stone;

        public Node(int x, int y, int w, int st, int stone) {
            this.x = x;
            this.y = y;
            this.w = w;
            this.st = st;
            this.stone = stone;
        }
    }
}
